package 回溯;

import java.util.ArrayList;
import java.util.List;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 括号生成.java
 * @Description TODO
 * @createTime 2020年11月04日 11:29:00
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 *
 *  
 *
 * 示例：
 *
 * 输入：n = 3
 * 输出：[
 *        "((()))",
 *        "(()())",
 *        "(())()",
 *        "()(())",
 *        "()()()"
 *      ]
 *
 * 思路：只要保证左括号的数量大于右括号的数量 即可
 */
public class 括号生成 {
    class Solution {
        //左括号的数量一定要大于右括号的数量
        //每个点都检测 一旦不符合就立即终止
        List<String> res=new ArrayList<>();

        public List<String> generateParenthesis(int n) {

            back(n,n,"");
            return res;
        }

        void back(int left,int right, String s){
            if(left==0&&right==0){
                res.add(s);
                return ;
            }

            if (left > right) {
                return;
            }

            if (left > 0) {
                back(left-1, right, s+"(");
            }

            if (right > 0) {
                back(left, right-1, s+")" );
            }
        }
    }
}
